package com.sgg.algorithm.sort;

import com.sgg.algorithm.sort.util.CommonUtil;

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int size = 10;
        int[] arr = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i] = (int) (Math.random() * size*10);
        }
        System.out.println("before" + Arrays.toString(arr));
        sort(arr);
        System.out.println("after" + Arrays.toString(arr));
        System.out.println(CommonUtil.isSort(arr));
    }

    public static void sort(int[] arr) {
        doSort(arr, 0, arr.length);
    }

    public static void doSort(int[] arr, int left, int right) {
        if (right - left < 2) {
            return;
        }
        int mid = pivotIndex(arr, left, right);
        doSort(arr, left, mid);
        doSort(arr, mid + 1, right);
    }

    private static int pivotIndex(int[] arr, int left, int right) {
        int temp = arr[left];
        right--;
        while (left < right) {
            while (left < right) {
                if (temp < arr[right]) {
                    right--;
                } else {
                    arr[left++] = arr[right];
                    break;
                }
            }
            while (left < right) {
                if (temp > arr[left]) {
                    left++;
                } else {
                    arr[right--] = arr[left];
                    break;
                }
            }
        }
        arr[left] = temp;
        return left;
    }

}
